One prior computer architecture technique for increasing computer performance uses multitasking. Multitasking is the ability to execute more than one application program or task at a time. Another prior computer architecture technique for increasing computer performance is the use of multiple microprocessors. Multitasking can be used in either a single processor system or a multiprocessor system.
One problem of multitasking systems is the allocation of system resources between tasks. For example, if two processes are requesting a disk, tape, or file, the system should guarantee that both do not attempt to use it at the same time. In other words, mutual exclusion between system resources should be guaranteed. One prior solution to this problem is the use of semaphores. Semaphores are special flags that are accessed and changed in an indivisible operation.
In certain prior systems, a register or a memory byte is used as a semaphore flag. If the semaphore flag is set, this indicates that the resource is busy or in use. If the semaphore flag is clear, this indicates that the resource is available. A processor reads the semaphore flag to determine if the resource is free. If the flag is clear, the processor begins using the resource and sets the semaphore flag. The processor clears the semaphore flag after the processor is done using the resource.
The read/modify/write cycle for the semaphore flag is made indivisible. The read/modify/write cycle is also referred to as a test and set operation. If the read/modify/write cycle of the flag were not indivisible, then two processors could read the same flag, and each could determine that the semaphore flag was free and conclude that the system resource was free. This, of course, would be incorrect. Thus, when the semaphore flag is read, no other process or processor in the system can be allowed to access memory until the read/modify/write cycle is complete. The 80386 microprocessor sold by Intel Corporation of Santa Clara, Calif. is an example of a prior processor using the above-described test and set operation. On the 80386 microprocessor, the semaphore flag is a memory byte. Certain prior Reduced Instruction Set Computer ("RISC") processors also use the above-described test and set operation.
The 80386 microprocessor allocates system resources in connection with multitasking through the use of the LOCK instruction prefix. The use of the LOCK prefix is also referred to as a LOCK exchange. On the 80386 microprocessor, an instruction with a LOCK prefix locks the memory for the duration of the instruction to guarantee that the read/modify/write cycle is indivisible. No other processor in the system can access memory until this instruction is complete. Thus, the requisite indivisibility is met. On the 80386 microprocessor, the LOCK prefix can be used only with the following instructions: Add With Carry ("ADC"), Integer Addition ("ADD"), And ("AND"), Bit Test ("BT"), Bit Test and Set ("BTS"), Bit Test and Reset ("BTR"), Bit Test and Complement ("BTC"), Inclusive Or ("OR"), Subtract With Borrow ("SBB"), Subtract ("SUB"), Exclusive Or ("XOR"), Exchange ("XCHG"), Decrement ("DEC"), Increment ("INC"), Negate ("NEG"), and Not ("NOT"). If a LOCK prefix is used with any instruction not on the preceding list, an invalid opcode exception is raised.
One disadvantage of this prior implementation of the LOCK instruction prefix is that it does not work efficiently. If a semaphore is not free when the semaphore is requested, a loop is entered without end until the semaphore is free. This is referred to as "busy waiting," and the loop is referred to as a "spin loop." Such a spin loop is relatively expensive in terms of time because the loop ties up the central processing unit and memory resources while waiting for the semaphore to free. One prior way to overcome this problem is to redefine the semaphore operators to place a process waiting for a free semaphore into a waiting queue and then call a scheduler to execute a different process while waiting for the semaphore. Another prior way to overcome this problem is to implement a counter and a spin loop.
Another disadvantage of the 80386 implementation with respect to the LOCK instruction prefix is that it only applies to the instructions or operations set forth above, which are each test and set (i.e., read/modify/write) instructions. The 80386 LOCK instruction prefix does not apply to operations more complex than test and set operations, such as compare operations or jump (i.e., branch) operations. Another operation more complex than the test and set operation is a compare and swap operation that uses a linked list. In such a compare and swap operation, there is a new element in the list. Therefore, the pointer in memory must be updated. The pointer is not a flag or semaphore.
Operations more complex than test and set operations are, however, used in multitask and multiprocessor digital systems. Therefore, there exists the problem of system allocation for multitasking when operations more complex than test and set operations are used.
Some prior processors overcome the problem of multitasking system allocation for instructions more complex than test and set operations by creating certain new instructions. One disadvantage of this prior approach is that the end result is a relatively complicated sequence of operations that need to be performed. The sequence of operations is complicated because special instructions are needed for different situations and it is difficult to consider all the situations that could arise. Another disadvantage of this approach is that it leads to additional instructions, which is contrary to the goal of a RISC processor of reducing the instruction set of the processor.